package template;

import java.util.HashSet;
import java.util.Set;

public class DictAndString {
    public static void main(String[] args) {
        m1();//判断字符串随意分割后能不能在一个字符串数组中找到


    }

    private static void m1() {
        Set<String> set=new HashSet<>();
        set.add("hello");
        set.add("i");
        set.add("like");
        set.add("eat");
        set.add("world");
        set.add("code");
        set.add("leet");

        System.out.println(wordBreak("likeicode",set));
    }

    public  static boolean wordBreak(String s, Set<String> dict) {
        int len = s.length();
       //默认值均为false
        boolean[] dp = new boolean[len + 1];//dp[i]代表前i个字符分割后能否在set中找到
        dp[0] = true;
        for(int i = 1; i <= len; i++){
            for(int j = 0; j < i; j++){//j代表字符串起始位置
                if(dp[j] && dict.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
}
